HW#4 --- last modified February 17 2019 19:23:27..

Solution set.

Due date: May 2

Files to be submitted:
  Hw4.zip

Purpose: To gain experience with the Turing Machine model.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO9 -- Construct a Turing machine accepting some simple languages.

Specification:

Do the following problems: Problems which involve writing as part of the solution should be in a file Hw4.pdf within Hw4.zip. If a problem involves JFLAP include the JFLAP file in the Hw4.zip.

1. Build a `1`-tape TM in JFLAP which on input `w` over the alphabet `{a, b, c}` outputs `w^R#w`.
2. Using pen and paper (not JFLAP) write down the machine that would result from the method of class for simulating the machine of the previous example with a machine that has only a semi-infinite tape.
3. Using JFLAP, build a Turing machine which on input `x#y` where `x` and `y` are binary numbers outputs their sum in binary. Use this machine in as a module of JFLAP which computes the product of `x` and `y`.
4. Consider the class of languages of the form `{w | exists y, w#y in R}` where `R` is a decidable language. Show this class of languages is exactly the same as the Turing Recognizable languages. If instead of `R` being decidable we had only allowed `R` to be context-free, would the result still hold? Explain your reasoning. What about if `R` had been regular?
5. Given a k-tape nondeterministic TM that runs in time `f(n)`, show how to simulate it with a 1-tape nondeterministic TM in time `O((f(n))^2)`.

Point Breakdown